import java.util.*;

public final class MaxSumTest
{
    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum1( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                    thisSum += a[ k ];

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }

        return maxSum;
    }

    /**
     * Quadratic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum2( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
        {
            int thisSum = 0;
            for( int j = i; j < a.length; j++ )
            {
                thisSum += a[ j ];

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }

        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

    /**
     * Simple test program.
     */
    public static void main( String [ ] args )
    {
      int a[ ] = {};
      int maxSum = 0;

	for (int N = 100; N < 2000000; N *= 2) {
	a = new int[N];
	Random r = new Random();
	for (int i = 0; i < N; i++)
	    a[i] = r.nextInt(N+1) - N/2;

	long start, end;
	long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;

	/*
	*/
	start = System.currentTimeMillis();
        maxSum = maxSubSum1( a );
	end = System.currentTimeMillis();

	elapsed1 = end - start;
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );

	start = System.currentTimeMillis();
        maxSum = maxSubSum2( a );
	end = System.currentTimeMillis();

	elapsed2 = end - start;
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );

	start = System.currentTimeMillis();
        maxSum = maxSubSum3( a );
	end = System.currentTimeMillis();

	elapsed3 = end - start;
        System.out.println( "Max sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );

	System.out.println("size: " + N + "\t" + "times: " + "\t" + 
			   elapsed1 + "\t" + elapsed2 + "\t" + elapsed3);

	/*
	System.out.println("time1/N^3: " + (double)elapsed1/((double)N*N*N));
	System.out.println("time2/N^2: " + (double)elapsed2/((double)N*N));
	System.out.println("time3/N: " + (double)elapsed3/((double)N));
	*/
	}
    }
}